/**

https://leetcode-cn.com/problems/number-of-enclaves/

1020. 飞地的数量
给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。

一次 移动 是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。

返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。



示例 1：


输入：grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
输出：3
解释：有三个 1 被 0 包围。一个 1 没有被包围，因为它在边界上。
示例 2：


输入：grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
输出：0
解释：所有 1 都在边界上或可以到达边界。


提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 500
grid[i][j] 的值为 0 或 1


202202121317
**/

package main

import "fmt"

type point struct {
	x int
	y int
}

var dirs = [][]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}

/**
使用bfs的思想，将外圈为1的点作为队列元素
然后进行扩散，这样所有连通的点都能遍历到

再次遍历内框，没有被遍历到的点就是飞地了

**/
func numEnclaves(grid [][]int) int {
	res := 0
	m, n := len(grid), len(grid[0])
	maps := make([][]bool, m)
	for i := range maps {
		maps[i] = make([]bool, n)
	}
	queue := []*point{}

	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if i == 0 || j == 0 || i == m-1 || j == n-1 {
				if grid[i][j] == 1 {
					queue = append(queue, &point{i, j})
					maps[i][j] = true
				}
			}
		}
	}

	for len(queue) > 0 {
		p := queue[0]
		queue = queue[1:]
		dx, dy := p.x, p.y
		for _, v := range dirs {
			nx, ny := dx+v[0], dy+v[1]
			if nx < 0 || nx >= m || ny < 0 || ny >= n || grid[nx][ny] == 0 {
				continue
			}
			if maps[nx][ny] == true {
				continue
			}
			maps[nx][ny] = true
			queue = append(queue, &point{nx, ny})
		}
	}

	for i := 1; i < m-1; i++ {
		for j := 1; j < n-1; j++ {
			if grid[i][j] == 1 && !maps[i][j] {
				res++
			}
		}
	}

	return res
}

func main() {
	fmt.Println(numEnclaves([][]int{{0, 0, 0, 1, 1, 1, 0, 1, 0, 0},
		{1, 1, 0, 0, 0, 1, 0, 1, 1, 1},
		{0, 0, 0, 1, 1, 1, 0, 1, 0, 0},
		{0, 1, 1, 0, 0, 0, 1, 0, 1, 0},
		{0, 1, 1, 1, 1, 1, 0, 0, 1, 0},
		{0, 0, 1, 0, 1, 1, 1, 1, 0, 1},
		{0, 1, 1, 0, 0, 0, 1, 1, 1, 1},
		{0, 0, 1, 0, 0, 1, 0, 1, 0, 1},
		{1, 0, 1, 0, 1, 1, 0, 0, 0, 0},
		{0, 0, 0, 0, 1, 1, 0, 0, 0, 1}}))

	//fmt.Println(numEnclaves([][]int{{0, 0, 0, 0}, {1, 0, 1, 0}, {0, 1, 1, 0}, {0, 0, 0, 0}}))
	//fmt.Println(numEnclaves([][]int{{0, 1, 1, 0}, {0, 0, 1, 0}, {0, 0, 1, 0}, {0, 0, 0, 0}}))

}
